#include <stdio.h>
#include <string.h>
#include <stdlib.h>


void buildNext(char* pattern, int* next,int subLen){
    next[0] = 0;
    for(int i = 1 ,j = 0; i < subLen; i++){
        while(j > 0 && pattern[i] != pattern[j]){
            j = next[j-1];
        }
        if(pattern[i] == pattern[j]){
            j++;
        }
        next[i] = j;
    }
}

int KMP_set(char* text,char* pattern){
    if(pattern == NULL || strlen(pattern) == 0){
        return 0;
    }
    if(pattern == NULL || strlen(pattern) > strlen(text)){
        return -1;
    }

    int lenT = strlen(text);
    int lenP = strlen(pattern);
    int *next = (int* )malloc(lenP* sizeof(int));

    buildNext(pattern,next,lenP);
    
    int j = 0;
    for(int i = 0;i < lenT; i++){
        while(j > 0 && text[i]!= pattern[j]){
            j = next[j-1];
        }
        if(text[i] == pattern[j]) {
            j++;
        }
        if(j == lenP) {
            free(next);
            return i - j + 1;
        }
    }  
    free(next);
    return -1;
}


// 暴力解法 
int lYS_vo(char* text,char* sub){
    if(text == NULL ){
        return -1;
    }
    if(strlen(text) < strlen(sub)){
        return -1;
    }

    int lenT = strlen(text);
    int lenS = strlen(sub);

    int i = 0;
    int j = 0;
    while(i < lenT && j < lenS){
        if(text[i] == sub[j]){
            i++;
            j++;
        }else{
            i = i - j +1;
            j = 0;
        }
    }
    if(j == lenS){
        return i-j;
    }
    return -1;
}

int main(){
    char*  str1 = "ABCDEFS";
    char* str2 = "DEF";
    printf("%d",KMP_set(str1,str2));

}

